perm filename STRUCT.DOC[SYS,HE]3 blob
sn#063847 filedate 1973-09-24 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00017 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 DISPLAY ROUTINES
C00006 00003 SAVE/RESTORE MECHANISM
C00007 00004 PROTOTYPE DATA STRUCTURES - variables,lines and body structure
C00011 00005 PROTOTYPES CONT. - feature structure
C00014 00006 PROTOTYPES CONT. - more feature structure
C00017 00007 EDGE DATA STRUCTURE
C00021 00008 LINE DATA STRUCTURE
C00025 00009 VERTEX DATA STRUCTURE
C00029 00010 SCENE FEATURE DATA STRUCTURES
C00031 00011 XREF TABLES
C00032 00012 MAPTRC WORD
C00035 00013 LFDIF AND MODIF FORMATS
C00037 00014 PARSER ARRAYS
C00043 00015 VARIABLES - PROCEDURE PARSE
C00046 00016 VARIABLES - PROCEDURE MAPREC
C00049 00017 VARIABLES - MAPREC - Central loop
C00052 ENDMK
C⊗;
DISPLAY ROUTINES
Only active portions of data structure are displayed.
All POGs are stored in one buffer, in order. The first word
for each POG is size/brightness word if POG is active and to be displayed;
it is a jump to the start of the next POG if inactive or already displayed.
DADR[I] is the index into the buffer for the start of the Ith POG.
DBRSI[I] is the size/brightness word for POG to store when POG becomes
active
DICH[I] is true if POG must be regenerated I=0 refers to all POGs
DION[I] is true if POG is being displayed.e displayed.
DISP[I] is true if POG is to be displayed.
DISFUS is index of first word of user generated display in buffer
DISLAS is number of user generated words in buffer
DFORCE true forces necessary updating (overrides NODIS and DHOLD)
DHOLD true suppresses display updating (user controlled)
NODIS true suppresses display updating (program controlled). Used
during data structure expansion.
POG WHAT WHERE
1 frame 4 to 13
2 edge pairs 14 to y←55+NOEPL+NOEPL%10
3 edge marks y+1 to j←y+210
4 lines j+1 to k←j+MAXNOV+5
5 line marks k+1 to l←k+MAXNOV+5
6 vertices l+1 to m←l+2*MAXNOV+5
7 m+1 end of used portion of buffer (DADR only)
Edge pairs are displayed as points if IAEDG≠2, else as line segments.
Vertices are displayed for line ends if CVLIN
DRX, DRY is center of display rectangle
IRX, IRY is center of internal coordinate rectangle
DSCX, DSCY are scale factors for display coordinates
ISCX, ISCY are inverse of DSCX, DSCY
If windowing (WIND true) edge points and strings are displayed if
-510≤x≤510 and (-510 max LOCT+5)≤y≤510, where LOCT is top of page printer.
Lines are displayed if ?????.
SAVE/RESTORE MECHANISM
file extensions set to .TEM during initialization and whenever
the data structure for the extension is altered. Automatic
saves are skipped when extension is not .TEM.
Automatic restores delete file if extension is .TEM.
If extension is .TEM, automatic saves use files
EDSAVE.TEM for edges
LISAVE.TEM for lines
PRSAVE.TEM for prototypes
For edge data input extensions are:
.DAT Hueckel format
.EDG Pingle format
.SED sorted file (transform and RDEP only entered)
.TEM temporary save file
PROTOTYPE DATA STRUCTURES - variables,lines and body structure
MXNPRO 5 maximum number of prototypes
MAXPLT 12*MXNPRO maximum number of prototype lines
MAXPFT 4*MAXPLT maximum number of prototype features
NPRO number of prototypes (free storage at NPRO+1)
PVERT number of vertices
PPTRL points to start of the prototype in PLINE AND PLINEF
PLTOT total number of prototype lines (free storage at
PLTOT+1)
PFTOT total number of prototype features stored (free
storage at PFTOT+1) =PLFTOT+PCFTOT
MAXPLS maximum number of lines/prototype
MAXPVS maximum number of vertices/prototype
PLFTOT total number of line features
PCFTOT total number of compound features
PFFREE feature to prototype free storage pointer
PFREE prototype c.f. pairs free storage pointer
indexed by prototype number
STRING PNAME[1:MXNPRO] prototype name
INT. PLINES[1:MXNPRO] number of lines for each prototype
INT. PVERTS[1:MXNPRO] number of vertices for each prototype
INT. PPTRL[1:MXNPRO] for each prototype, the index of the first word in
prototype line arrays which refer to this prototype
for each line of prototype. If line I is in prototype J, the index
is PPTR[J]+LEDG1[I]. Data for prototype I starts at PPTRL[I] and
extends for PLINES[I] entries.
INT. PLINE[1:MAXPLT] line data structure - cross reference
0-5 6B end vertex 1 (unique number
for each seperate vertex)
6-11 6B end vertex 2
12-17 6B ptr into these tables to next
line at end 1
18-23 6B ptr to next line at end 2
24 1B side 1 border?
25 1B side 2 border?
26-30 5B equivalence class
31-35 5B parallelity class (0 for all
lines || to no other)
INT. PLINE2[1:MAXPLT] 0-25 26B not used
26 1B on iff this line in the longer
(of 2) length classes for this
line's parallelity class.
27-35 9B l.f. ID.
INT. PLINEF[1:MAXPLT] line features. Bit 0 on iff l.f. non-directional
Also found in PFLST
PROTOTYPES CONT. - feature structure
indexed by feature I.D.
INTEGER PFLST[1:MAXPFT] is an ordered array of all different features for
all prototypes. L.Fs are stored first, followed by
C.F.s. Each type is ordered by magnitude.
line feature storage. One half word for the line
feature traversing the line in each direction.
Ordered with the smallest l.f. on the left.
0 1B 0
1-4 4B # of lines >180 degrees
5 1B any of the above ~ = 180 degrees?
6-9 4B # of lines < 180 degrees
10 1B any of the above ~ = 180 degrees?
11-12 2B outside angle (smallest angle from
line on the >180 side to the ≤180
side. Bits codes as:
0 <180
1 ≤180
2 >180
3 ≥180
13-14 2B 0 if converging on this side
1 if conv. or ||
2 if diverging on this side
3 if div. or ||
based on angle from last line at
start end for this side, to next
line at opposite end CCW ordered
as the l.f.
15-17 3B unused
compound feature storage. One half word for
each direction of the line pair. Ordered with
the smallest c.f. on the left.
0 1B 1
1-8 8B L.F. id for first line in this
direction.
9 1B direction that L.F. is traversed
going toward the junction: 0 as
ordered in L.F.; 1 otherwise.
10-13 4B position of other parent line CCW
around center vertex. 1+number of
rays in between
14-17 4B constellation of opposing end-rays
as for L.F.s
14 1 if intersect pointing out
from C.F.
15 1 if diverging on this side
16 1 if collinear
17 1 if parallel
PROTOTYPES CONT. - more feature structure
INT. PFPTR[0:MAXPFT] feature reference word
0 1B all mappings tried?
1-5 5B # of rays for this feature
6 1B ordered?
7-11 5B unused
12-23 12B points into CFEAT (c.f.s only)
start of list of instances of
this feature in scene.
24-35 12B pointer into PFPRO. Start of list
of instances of this feature in
prototypes.
INT. PFPRO[1:MAXPFT] prototype substructure.
0-11 12B prototype number
12-23 12B pointer to PFEAT - instances of
this feature in this prototype
24-35 12B pointer to next entry for this
feature in some other prototype.
0 at end of list.
INT. PFEAT[1:MAXPFT] has in each first word:
0 1B 1
1-11 11B prototype number
12-23 12B feature i.d.
24-35 12B # of items in sublist
followed by items. If c.f. :
0 1B 0
1 1B 0 if left half of LF define line
end at intersection; 1 otherwise
2-11 10B index of prototype line 1
12 1B 1
13 1B line 2 end at intersection (as bit 1)
14-23 10B index of prototype line 2
24-35 12B next pointer.
If l.f.:
0 1B 0
1-11 11B index of prototype line
12 1B 0
13-23 11B equivalance class
24-35 12B next pointer. Last pointer is 0.
EDGE DATA STRUCTURE
EDGMIN 200 minimum size of NOEPA for allocating arrays
NOEPM 50
NOEPA 0 number of edge pairs
NOEPL NOEPA+NOEPM
KICH read in length of camera transform
RDEP read in operator spacing/2 (length of edge pairs)
REAL ARRAY EAX[0:NOEPL] x coord of start of edge pair
REAL ARRAY EAY[0:NOEPL] y coord of start of edge pair
REAL ARRAY EBX[0:NOEPL] x coord of end of edge pair
REAL ARRAY EBY[0:NOEPL] y coord of end of edge pair
INTEGER ARRAY LE[0:NOEPL] edge pair connectivity. =1 if not linked,
=2 if linked to previous pair, =3 if linked to
next pair, =4 if linked to both pairs.
REAL ARRAY TFORM[1:15,1:3] camera transform
no edge pairs if EAX[0]=EAY[0]=0
LINE DATA STRUCTURE
LINMIN 50 minumum size of NOBAL for array allocation
MSAFA 30 absolute margin of safety (# of lines extra)
RMSAF .5 relative margin of safety
NOBAL NOEPA*RDEP/10 # of initial lines, estimate based on edges
MAXNOL NOBAL+NOBAL*RMSAF+MSAFA maximum number of lines
Arrays of length MAXNOL are ordered by line number and the index is the
I.D. of the line. The indices of the vertices of the line in the simple
vertex arrays are 2*I-1 and 2*I.
NOL number of lines
IFREEL pointer to first free line storage in LCREDE (none iff ifreel=0)
LDATE current level for activation-deactivation.
LNCRE1 lowest active level
LNCRE2 highest active level
REAL CXL[1:MAXNOL] line equation X*CX+Y*CY+CC=0
REAL CYL[1:MAXNOL] line equation
REAL CCL[1:MAXNOL] line equation
REAL RLEN[1:MAXNOL] line lengths
REAL ANGARG[1:MAXNOL] pos. angle ( in degrees) from pos. abscissa
INT. LEDG1[1:MAXNOL] pointer to start of edge data structure for scene
lines
INT. LEDG2[1:MAXNOL] pointer to end of edge data structure for scene
lines.
INT. LCREDE[1:MAXNOL] line creation-deletion vector. Low 12 bits are
current value. Parser uses as 3-number stack by
rotating word 12 bits at a time.
N≤-1000 means free storage. If -1000-P then P is
index of next free word. LCREDE[last]=-1000
-1000<N≤0 not currently used.
N>0 means created at level N (1 is init. fit)
and line is active (if between LNCRE1 and LNCRE2).
0<N≤1000 is the scene
1001 is scene lines used in current MAPREC
1002 is inserted lines or rays in current MAPREC
1003 is replaced lines or rays in current MAPREC
1004 is inserted lines or rays for best mapping
so far with current key (MAP)
1005 is inserted lines or rays for best total
mapping so far (PARSE)
1006 is display
1007 is unused scene lines at mapped vertices
2000+CURMAP complete objects or best partials
3000+CURMAP removed lines (replaced by insertions)
of complete objects or best partials
≥4000 is free so far (12 bits only)
VERTEX DATA STRUCTURE
MAXNOV 2*MAXNOL maximum number of composite and single verticies
MAXSCF 2*MAXNOV maximum number of compound features.
for composite vertices
NOV number of composite vertices
IFREEV pointer to first free vertex storage (none iff ifreel=0)
REAL XVCOR[1:MAXNOV] x coordinate of composite vertex. Indexed by c.v. #
REAL YVCOR[1:MAXNOV] y coordinate of vertex
INT. LVERSI[1:MAXNOV] points to one of its single vertices.
(<0 if free storage). If -1000-p then p is index
of next free word and LVERSI[last]=-1000. Indexed
like XVCOR and YVCOR.
for single vertices
The array index is the vertex number. For vertex I, the index in the arrays
of the line data structure for its line is (I+1) DIV 2.
REAL XLCOR[1:MAXNOV] x coordinates of vertices of line
REAL YLCOR[1:MAXNOV] y coordinates of vertices of line
INT. LVER[1:MAXNOV] points to next s.v. around c.v. ccw. Inactive
lines may still point to c.v.s so LCREDE must
be checked. LVER[y]=y iff free line-end
(SVANG is then =360.) N>0 iff
vertex is permanentεc.v and next linked to s.v.is
# N. N<0 iff vertex is temporaryεc.v. and next
linked to s.v. is #-N. This is true also for
inactive lines.
INT. LVERCO[1:MAXNOV] Pointers from all members of a composite vertex to
that vertex (0 for dead cv's-vertex is free).
For s.v. n, coordinates of its cv are in
XVCOR[LVERCO[n]] and YVCOR[LVERCO[n]].
REAL SVANG[1:MAXNOV] angles at vertices to next line in list.
INTEGER LINK[1:MAXNOV] points to nearest vertex of the line collinear
to the line of this vertex. 0 if none.
If there are intervening lines, the links
are negative. Links are formed on the basis of
objects.
SCENE FEATURE DATA STRUCTURES
scene feature data structure:
SCF number of c.f.s in scene
INT.CFEAT[1:MAXSCF] 0 1B L1 end at intersection
1-11 11B i.d. of line 1
12 1B L2 end at intersection
13-23 11B i.d. of line 2
24-35 12B pointer to next CFEAT entry
for this c.f.
INT. LFEAT[1:MAXNOL] line features (index by line number). 0 if no l.f. in
central table for this line. Negated if l.f. is
ordered contrary to prototype line (not if partially
similar l.f.).
0 1B 1 if partially similar l.f.
1 1B if partially similar l.f., 1 if 2nd
vertex ok, 1st
amended; 0 if vica versa.
2 1B 1 if ordered contrary to scene line
3-35 33B i.d. of l.f.
XREF TABLES
collinear lines :
RCOL[V] distance to center of gap
lines intersect outside
RAS[V] distance to intersection from vertex v
RBS[V] distance to intersection from other vertex
IPS[V] # of closest vertex of other line, negative if collinear
lines intersect inside second of them
RK[V] distance to intersection from first vertex, V
=-1 if this line wholely inside other line
RBK[V] distance from intersection to closest vertex of other line
IPK[V] closest vertex # on other line
MAPTRC WORD
This word is read in octal and consists of flag bits for parser and
mapping routines. The original value is the argument to the parse command.
The codes are read in a as string of letters (no blanks between them) and
decoded. PI means pause and input new string. It turns on the pause bit
for the bit immediately preceding it. It is illegal for those bits not
having pause bits. RESET returns -1 and NULL returns 0.
Codes not recognized are typed and a new string is requested; the input
TTY buffer is cleared before this input.
After a pause : causes continuation of the program and ←n: causes
continuation after decoding n as new MAPTRC string
BIT CODE WORD DESCRIPTION
35 NR 1 display each new ray
34 2 pause after 35
33 OV 4 display each orbited vertex
32 10 pause after 33
31 PM 20 display each partial mapping
30 40 pause after 31
29 BM 100 display best mapping for each key
28 200 pause after 29
27 BP 400 display each best partial (parse)
26 1000 pause after 27
25 TT 2000 trace output to TTY
24 4000 pause after 25
23 TD 10000 trace output to PARSnn.TRC
22 PK 20000 pause after each new key
21 TL 40000 type trace line number
20 PD 100000 plot display
19 SK 200000 display scene after best mapping for each key
18 400000 pause after 19
17 SI 1000000 display scene for each isolation
16 2000000 pause after 17
15 PR 4000000 do PRINT REGREF 11 after each isolation
If MAPTRC=-1, the previous analysis is flushed so the parse can be redone
and MAPTRC←0. DO NOT USE.
LFDIF AND MODIF FORMATS
LFDIF: NOT USED
0 1B 1 if change (meaningful only for || case) * 1st position
1 1B 1 if deletion, 0 if insertion *
2 1B 1 if ||, 0 if div/conv *
3 1B 1 if deletion, 0 if insertion . other positions
4-7 4B number of lines to be inserted/deleted .
8-11 4B start position +according to which lines .
+of the vertex the first .
12-15 4B end position +and last positions would .
+correspond to after alter-.
+ing the special line .
16-17 2B character tags
0 no lines, no change
1 lines, no change
10 change, unambiguous
11 change, ambiguous
same for other side
MODIF:
high order 2 bits:
1 if ambiguous
1 if bare before insertion
followed by two bit positions for each ray at this vertex
00 if no change
01 if insert new ray
10 if delete present ray
11 if ambiguous
PARSER ARRAYS
matching template:
PARCLA[1:PLIN] parallelity class for each line of prototype
LENCAT[1:PLIN] length class for each line of prototype
LENDV[1:PLIN,0:1] for each line of prototype, the number of the
vertex at each end
LENDP[1:PLIN,0:1] for each line of prototype, the index of the
next line CCW around each vertex
recursive structure:
MAPORD[1:PLIN] the prototype lines referenced so far, in time
order.
MPORDS[1:2*PLIN] indexed by recursive level and contains pointers
to the currently referenced MAPORD entries at
each level.
MAPIS[1:2*PLIN] indexed by recursive level and contains pointers
to the last MAPORD items created at the level.
record mappings:
PLMAP[1:MAXPLS,0:1] for each prototype line end, the corresponding
scene line end (s.v.). Ends are ordered according
to feature. '7777 stored if no direction known and
not mapped yet.
LLEV[1:PLIN,0:1] recursive level of corresponding mapping in PLMAP
negative for attempted INCOV. Clear to init.
PLMAPO[1:PLIN,0:1] 1 level PDL for PLMAP during line replacement
LLEVO[1:PLIN,0:1] 1 level PDL for LLEV during line replacement
PVMAP[1:MAXPVS] for each prototype vertex, the corresponding
scene composite vertex. Clear to init.
VLEV[1:PVER] recursive level of corresponding mapping in PVMAP
line fusion:
LFUSE[1:PLIN,0:1] a 6-level stack, for each prototype line,
containing pointers into LFUSES. Points to LFUSES
entry, if any, for this line.
LFUSES[1:63] Backup info for fusion.
0-23 SV of line extended (opposite fused end)
24-35 SV of new line corresponding to above
misc.:
LENARG[0:PLIN,0:1,0:1] Indexed by ||-class, conv. or div. and leng. class
Contains length of other lines of this type, if
any have been found.
PARARG[0:PLIN] Inited to -1. Angle of lines in this || class, if
any have been found previously.
RRR[0:1] Internal to PARUP
RNUM[0:1] Internal to PARUP
EVA[1:PLIN] Holds score for each line of mapping being graded
INSLEV[1:PLIN] recursive level of inserted line. Negative if temp.
LFTSTL[1:PLIN] recursive level where l.f. consistancy test true if≠0
to save best mappings:
PARTS[1:63,0:1+MAXPLS%3] first index is mapping number, second is scene line
numbers corresponding to prototype lines stored 3 per
word starting in word 1. -1 if no such line.
word 0 contains:
0-5 6B prototype number
6-8 3B completion code
00 complete
01 partial - no completion
11 partial - completion attempted
10 completed partial
9-35 27B score for mapping
FLMAPS[1:MAXNOV] mapping keys stored, in time order during c.f. pass
0-10 11B scene line #
11-22 12B prototype #
23-34 12B prototype line #
35 1B 1 scene and prototype lines ordered
differently.
LEDG1 indexed by scene line
-1 if line is ray
1 if LEDG1 for other line at INCOV using this line
is ≥0 and lne is very short or LEDG2=-2 for it
2 ????
3 if line was created by fusing
LEDG2 -2 if line created by INCOV or replacement and is
colinear with an unused line, or if INCOV, line is
shorter than the distance from the SV to the CV at
the end intersected.
VARIABLES - PROCEDURE PARSE
KMP display scene flag set by MAP procedure
FLMIND maximum used index in array FLMAPS
BESTMP index in PARTS of best mapping so far
CURMAP index in PARTS of last mapping saved
CMPIND index in PARTS of current mapping
UB upper bound of current feature search
LB lower bound of current feature search
UBI upper bound of line search when mapping LFs
FTSW 0 mapping CFs
1 mapping LFs ordered same as line
2 mapping LFs ordered opposite line
TC trace line counter
MXMXCM last feature mapped
MAXCOM feature currently being mapped
KADR index of current feature
CFP current position on linked list (in CFEAT) of instances of the
feature in the scene
ORD ≠0 if feature is ordered
SCL1 ID of line (1 for CF)
SCL2 Id of line 2 for CF
PRP current position on linked list (in PRPRO) of prototypes having
this feature
IC current CFEAT entry
PROT prototype number
AD0 index of first line of prototype
PLIN number of prototype lines
PVER number of prototype vertices
PFP current postion on sequention list (in PFEAT) of instances of
the feature in this prototype
IB current PFEAT entry.
PRL1 index of line in prototype (1 if CF)
PRL2 index of line 2 in prototype if CF
DIR CF: 1 if LF ordered contrary to ordering of line in CF
LF: 1 if LF ordered contrary to scene line
6 if LF ordered contrary to prototype line
7 if LF ordered contrary to both lines
SUCC value of MAP procedure
-1 failed
0 partial map
1 complete map
2 complete map with cut off lines
VARIABLES - PROCEDURE MAPREC
global variables:
LNCS1 save creation range at start of PARSE
LNCS2 "
RAYS number of lines>180 in current MODIF word
MDCNT number of non-zero bits (in pairs) in MODIF
DEGSW TRUE if mapping degenerate prototypes and DEGABL is TRUE
DEGABL always FALSE !!
FULREC settable flag for full recursion used in backing up levels
FTREV set by last feature creation
0 both halves of feature are equal
1 right half<left (feature has halves reversed)
2 right>left
RWIC colinearity threshold
RMALS maximum line shrinkage allowed
RELLF =.18 adjustment for length class checking.
RUL 0 if F-mapping (L.F. consistant mappings only)
1 if C-mapping (consequence mappings allowed)
BULEVS number of levels to back up
BAU TRUE if backing up (current line end is loose end of a ray-
will try to create a vertex by intersection)
CMPL -1 if object completed
0 if object not completed
1 if object completed by cutting lines in the scene
CMPLO holds last value of CMPL at termination of mapping; value from
previous mapping if CMPL was 1 at that point, causing mapping
to continue.
RLEV recursion level
MAPI maximum used entry in MAPORD. Reset from MAPIS during backup.
MPORD minimum entry of MAPORD currently being used. Reset from
MPORDS during backup.
BAUS TRUE if backing up. Set by backup routines if this state correct
at final level. Used to set BAU .
IRET value returned for MAPREC
DIR CF: 1 if LF ordered contrary to ordering of line in CF
LF: 1 if LF ordered contrary to scene line
LFDBT CF: = DIR
LF: 1 if scene line ordered contrary to prototype line
VARIABLES - MAPREC - Central loop
ID index in MAPORD of current proto base line
IB end of base line being processed
NDP end of current line at vertex during orbiting
IA I.D. of base line
NEWLP I.D. of current line during orbiting
VPR I.D. of proto vertex being orbited (end IB of IA)
NLSCM I.D. of scene line being mapped into base line
NEWLSC I.D. of scene line being mapped into current line during orbiting
NDSCM end of base scene line to be considered for mapping
NDSC end of current scene line at vertex being orbited.
IC I.D. of base scene SV to be orbited
PLND I.D. of SV at end of line begin orbited
NEWSV I.D of SV at end of current line being orbited
VSC I.D. of CV at end of line being orbited.
INCOV ≠0 if trying to create a vertex by intersecting lines
INCOVS ≠0 if current vertex created by intersecting lines
VL value of PREORB procedure
0 if INCOVS on or current vertex is not a consequence of full lines
-1 if vertex a consequence of full lines
-2 if current vertex is INCOVS
1 if vertex is contradictory (line mapped elsewhere)
INS ≠0 if inserting a ray when orbiting a vertex
RAY # of rays at current vertex, when orbiting it
CH ≠0 if orbited vertex needs testing
RAYCNT bareness check - # of rays of orbited vertex not counted inserted
RDIF difference between proto and scene line lengths
RP length of proto line
RSC length of scene line